package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/find-mode-in-binary-search-tree/">二叉搜索树中的众数(Find Mode in Binary Search Tree)</a>
 * <p>
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * 如果树中有不止一个众数，可以按 任意顺序 返回。</p>
 * <p>假定 BST 满足如下定义：
 * <ol>
 *     <li>结点左子树中所含节点的值<b>小于等于</b>当前节点的值</li>
 *     <li>结点右子树中所含节点的值<b>大于等于</b>当前节点的值</li>
 *     <li>左子树和右子树都是二叉搜索树</li>
 * </ol>
 * </p>
 * <pre>
 *     示例 1：
 *      输入：root = [1,null,2,2]
 *                  1
 *                   \
 *                    2
 *                   /
 *                  2
 *      输出：[2]
 *
 * 示例 2：
 *      输入：root = [0]
 *      输出：[0]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [1, 10^4] 内</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 * </ul>
 * <b>进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）</b>
 *
 * @author c2b
 * @since 2025/2/11 11:18
 */
public class LC0501FindModeInBinarySearchTree_S {

    static class Solution {
        private final List<Integer> resList = new ArrayList<>();
        private int maxFreq = 0;
        private int currFreq = 0;
        private int currNum = 0;

        public int[] findMode(TreeNode root) {
            dfs(root);
            int[] modes = new int[resList.size()];
            for (int i = 0; i < resList.size(); i++) {
                modes[i] = resList.get(i);
            }
            return modes;
        }

        /**
         * 二叉搜索树的中序遍历(左->根->右)是非递减的
         */
        private void dfs(TreeNode currNode) {
            if (currNode == null) {
                return;
            }
            dfs(currNode.left);
            if (currNum == currNode.val) {
                ++currFreq;
            } else {
                currFreq = 1;
                currNum = currNode.val;
            }
            if (currFreq == maxFreq) {
                resList.add(currNum);
            } else if (currFreq > maxFreq) {
                maxFreq = currFreq;
                resList.clear();
                resList.add(currNum);
            }
            dfs(currNode.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(2);
        root.right.left.right = new TreeNode(2);
        Solution solution = new Solution();
        Printer.printArrayInt(solution.findMode(root));
    }
}
